/*
 * @lc app=leetcode.cn id=206 lang=cpp
 *
 * [206] 反转链表
 *
 * https://leetcode-cn.com/problems/reverse-linked-list/description/
 *
 * algorithms
 * Easy (72.76%)
 * Likes:    2360
 * Dislikes: 0
 * Total Accepted:    925.3K
 * Total Submissions: 1.3M
 * Testcase Example:  '[1,2,3,4,5]'
 *
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：head = [1,2]
 * 输出：[2,1]
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：head = []
 * 输出：[]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 链表中节点的数目范围是 [0, 5000]
 * -5000 
 * 
 * 
 * 
 * 
 * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
 * 
 * 
 * 
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // ListNode* reverseList(ListNode* head) {

    //     pre cur temp
    //     ListNode* temp; //保存curd的下一个节点
    //     ListNode* cur = head; // 保存当前要反转的节点
    //     ListNode* pre = NULL; //保存当前要反转节点的上一个节点
    //     while(cur != NULL){
    //         temp = cur->next;
    //         cur->next = pre;
    //         pre = cur;
    //         cur = temp;
    //     }
    //     return pre;   
    // }

    // //递归解法 -->做的事情实际上就是不断让 前边的元素 指向后边紧挨的元素。 直至链表末尾
    // ListNode* reverse(ListNode* pre, ListNode* cur){
    //     if(cur == NULL) return pre; //递归的结束最终是正向链表的最后一个元素，也即是反向链表的第一个元素的指针
        
    //     ListNode* temp = cur->next;
    //     cur->next = pre;

    //     return reverse(cur, temp);
    // } 

    // ListNode* reverseList(ListNode* head) {

    //     return reverse(NULL, head);

    // }

    ListNode* reverseList(ListNode* head) {
        
        return reverse(nullptr, head);
    }

    ListNode* reverse(ListNode* pre, ListNode* cur)
    {
        if(cur == nullptr) return pre;

        ListNode* temp = cur->next;
        cur->next = pre;
        
        return reverse(cur, temp);
    }





    //递归解法 -->从后往前递归
    // ListNode* reverseList(ListNode* head){
    //     if(head == NULL) return NULL;
    //     if(head->next == NULL) return head;

    //     //开始递归，一直往后跑，找到读后一个节点（head->next = NULL，此时的head是最后一个节点） ，即是last
    //     //last = head
    //     ListNode* last = reverseList(head->next);

    //     //第一次递归 出来后，这里的head其实是最后一个节点的前一个节点
    //     //以下是说 head的下一个节点 所指向的下一个 即是自己，往回指        
    //     head->next->next = head;

    //     //而此时的head的下一个不再是后边的那个了，而是谁也不指，等待着跑出递归后，第一个节点指向空
    //     head->next = NULL;

    //     return last;

    // }





};
// @lc code=end

